1. Technical Field
The present invention relates to static timing analysis and, in particular, to block-based static timing analysis with uncertainty.
2. Description of Related Art
Static timing analysis (STA) is critical to the measurement and optimization of the performance of a circuit before its manufacture. Full chip static timing analysis is usually performed using efficient block-based techniques. A block-based approach allows incremental, embedded static timing analysis and therefore enables timing-driven flows in logic synthesis and physical design. Hence, block-based static timing analysis has emerged as one of the key technologies in current design methodologies.
The timing or performance of the chip is heavily dependent on the manufacturing process variations (e.g. Vt, Length, etc.) and design environment variations (e.g. VDD and temperature variations, noise impact on timing, etc.). As the feature sizes decrease, the ability to control the manufacturing spread or accuracy of a given feature size also decreases. Along with increased process variations, the uncertainty caused by design also increases. The increase of uncertainty in design is caused by increase of power supply and temperature variations and interconnect loading uncertainty such as coupling noise impact on timing. Another source of uncertainty is the inherent error in the gate delay models, also called the model-to-hardware correlation error. It is critical that these increased timing uncertainties be handled in the design process in an efficient and accurate manner. Given the pervasive nature of static timing, it is essential that a variation-aware static timing approach be suitable for full chip designs.
Design variations or uncertainty in static timing analysis is typically handled in two broad ways. The first set of techniques handle variations by worst casing the circuit response. In such a scenario, static timing is performed at various design corners (e.g. fast, slow and nominal design corners). For example, the fast corner is computed by placing all of the gates (or transistors) at the fast corner and performing a regular deterministic timing analysis. The timing results of the fast, slow, and nominal corners can also be combined to minimize the typically large error of worst-case analysis.
This approach is computationally attractive but can be inaccurate due to its worst-case nature. The worst-case approach has traditionally been used for industrial designs but is becoming inapplicable as the timing variations continue to increase. Furthermore, to account for intra-chip or local variations, these techniques scale the data and clock path delays differently using empirical factors.
The second way to handle variations in timing is to perform statistical timing analysis. Statistical static timing analysis has been well-studied. Reconvergent fanouts have caused several statistical timing analysis approaches to have exponential complexity. Efficient approximate techniques for reconvergent fanout are not addressed in these techniques. Block-based approaches to statistical STA have been proposed.
In one such approach, the delays of the gates and arrival times are modeled as independent discrete random variables. Reconvergent fanouts are not considered. False path analysis using this basic framework is considered in another approach. Yet another approach proposes a technique which computes both upper and lower bounds to the exact solution, in the presence of reconvergent fanouts. Further, the prior art approaches to block-based statistical static timing analysis show that statistical STA performed without accounting for reconvergent fanouts is an upper bound on the actual delay. However, their methods of enumerating selected nodes to obtain improved bounds may be cumbersome for large circuits, and have exponential runtime in the worst case.
A further drawback of these block-based approaches is that they model both gate delays and arrival times as discrete probability density functions or PDFs. This involves propagating impulse trains across the circuit and taking the statistical maximum of two arrival times, a fundamental operation in STA, becomes inefficient.
In contrast to the above block-based methods, a path-based approach has been proposed. Each path delay is modeled as a sum of individual gate delays with each gate delay being a function of random variables. By assuming small deviations from the nominal value, a linear statistical model for gate delay is constructed that can be efficiently summed up to get the path delay. However, to get the circuit delay a statistical maximum is performed assuming independent paths which is not true in general.
Another drawback of path-based approaches is that a large number of paths must be examined and can be exponential in the worst-case. Furthermore, path-based approaches are not amenable to incremental STA, a necessary requirement in the synthesis and optimization of designs. Some prior art path-based approaches perform circuit optimization in the presence of uncertainties by considering the large number of equally critical paths. However, these approaches do not include any technique for performing statistical STA.